package cn.edu.njust.alg.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import cn.edu.njust.utils.ListUtils;

/**
 * 创建时间：2015年6月15日 上午11:47:37 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Leetcode_0_t.java 类说明：
 */
public class Leetcode_94_Binary_Tree_Inorder_Traversal {

	public static List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode p = root;
		TreeNode q;
		while (p != null) {
			stack.push(p);
			p=p.left;
		}
		while (!stack.isEmpty()) {
			q = stack.pop();
			list.add(q.val);
			p = q.right;
			while (p != null) {
				stack.push(p);
				p=p.left;
			}
		}
		return list;
	}

	public static void main(String[] args) {
		int[] pr = { 1, 2, 3, 4, 5, 6, 7 };
		int[] in = { 3, 2, 1, 5, 4, 6, 7 };
		TreeNode root = Leetcode_105_Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal
				.buildTree(pr, in);
		List<Integer> list=inorderTraversal(root);
		ListUtils.printList(list);
		
		
	}

}
